package com.algorithm.Trie;

import com.algorithm.Map.HashMap;

/**
 * 字典树，前缀树
 * @param <V>
 */
public class Trie<V> {
    private int size;
    private Node<V> root;

    public int size() {
        return size;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public V add(String key, V value) {
        keyCheckNotNull(key);

        if (root == null) {
            root = new Node<>(null);
        }
        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            Character c = key.charAt(i);
            HashMap<Character,Node<V>> map = node.getChild();
            Node<V> characterNode = map.get(c);
            if (characterNode == null) {
                characterNode = new Node<>(node);
                characterNode.character = c;
                map.put(c,characterNode);
            }
            node = characterNode;
        }

        if (node.word) {
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        node.word = true;
        node.value = value;
        size++;
        return null;
    }

    public V remove(String key) {
        keyCheckNotNull(key);
        Node<V> node = node(key);
        if (node == null || !node.word) return null;
        size--;
        V oldValue = node.value;

        if (node.child != null && !node.child.isEmpty()) {
            node.word = false;
            node.value = null;
            return oldValue;
        }

        Node<V> parent;
        while ((parent = node.parent) != null) {
            parent.getChild().remove(node.character);
            if (parent.word || !parent.getChild().isEmpty()) break;
            node = parent;
        }
        return oldValue;
    }

    public V get(String key) {
        Node<V> node = node(key);
        return node != null && node.word ? node.value : null;
    }

    public boolean contains(String key) {
        Node<V> node = node(key);
        return node != null && node.word;
    }

    public boolean startsWith(String prefix) {
        return node(prefix) != null;
    }


    private Node<V> node(String key) {
        keyCheckNotNull(key);
        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            if (node == null || node.child == null || node.getChild().isEmpty()) return null;
            Character c = key.charAt(i);
            node = node.getChild().get(c);
        }
        return node;
    }

    private void keyCheckNotNull(String key) {
        if (key == null || key.length() == 0) {
            throw new IllegalArgumentException("key must be not null");
        }
    }

    private static class Node<V> {
        Node<V> parent;
        HashMap<Character,Node<V>> child;
        Character character;
        boolean word;
        V value;

        public Node(Node<V> parent) {
            this.parent = parent;
        }

        HashMap<Character,Node<V>> getChild() {
            if (child == null) { child = new HashMap<>(); }
            return child;
        }
    }
}
